package ch6.part3;

import java.util.HashMap;

/**
 * LRUCache算法实现，详情可参考JDK中的LRUCache，以及Redis中的LRU算法实现
 *
 * @author liuwanxiang
 * @version 2019/06/17
 */
public class MyLruCache {

    private Node head;
    private Node end;

    private int limit;
    private HashMap<String, Node> map;

    private MyLruCache(int limit) {
        this.limit = limit;
        this.map = new HashMap<>();
    }

    /**
     * 通过key值，查询value
     *
     * @param key key
     * @return 查询结果
     */
    private String get(String key) {
        Node node = map.get(key);
        if (node == null) {
            return null;
        }
        refreshNode(node);
        return node.value;
    }

    /**
     * 通过key-value的形式置数据
     *
     * @param key   key
     * @param value value
     */
    private void put(String key, String value) {
        Node node = map.get(key);
        if (node == null) {
            if (map.size() >= limit) {
                String oldKey = removeNode(head);
                map.remove(oldKey);
            }
            node = new Node(key, value);
            addNode(node);
            map.put(key, node);
        } else {
            node.value = value;
            refreshNode(node);
        }
    }

    /**
     * 根据key值删除数据
     *
     * @param key key
     */
    private void remove(String key) {
        Node node = map.remove(key);
        if (node != null) {
            removeNode(node);
        }
    }

    /**
     * 节点被访问过之后，刷新节点状态
     *
     * @param node 待刷新节点
     */
    private void refreshNode(Node node) {
        if (node == end) {
            return;
        }
        // 先删除节点
        removeNode(node);
        // 后新增节点
        addNode(node);
    }

    /**
     * 删除节点，并返回被删除节点的key值
     *
     * @param node 待删除节点
     * @return 被删除节点的key值
     */
    private String removeNode(Node node) {
        if (node == head && node == end) {
            head = null;
            end = null;
        } else if (node == head) {
            node.next.pre = null;
            head = node.next;
        } else if (node == end) {
            node.pre.next = null;
            end = node.pre;
        } else {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        return node.key;
    }

    /**
     * 添加节点，这里面有坑，务必要注意两处判空
     *
     * @param node 待添加的节点
     */
    private void addNode(Node node) {
        if (end != null) {
            end.next = node;
            node.pre = end;
            node.next = null;
        }
        end = node;
        if (head == null) {
            head = node;
        }
    }

    /**
     * 双向链表，节点对象
     */
    private static class Node {
        private Node pre;
        private Node next;
        private String key;
        private String value;

        Node(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        MyLruCache lruCache = new MyLruCache(5);
        lruCache.put("001", "用户1信息");
        lruCache.put("002", "用户2信息");
        lruCache.put("003", "用户3信息");
        lruCache.put("004", "用户4信息");
        lruCache.put("005", "用户5信息");
        lruCache.get("002");
        lruCache.put("004", "用户4信息更新");
        lruCache.put("006", "用户6信息");
        System.out.println(lruCache.get("001"));
        System.out.println(lruCache.get("006"));

    }

}
